Search results for "kvantu orākuls"

Kvantu algoritmi simbolu virkņu uzdevumiem

2021

Darbā tiek apskatīti trīs simbolu virkņu uzdevumi. Pirmais no tiem ir nosaukts ”vārda meklēšana tekstā”: dotajam tekstam 𝑠 garuma 𝑛 un vārdam 𝑡 garumā 𝑚, pateikt, vai vārds atro­ das tekstā. Klasiski šo var atrisināt laikā 𝑂(𝑛 + 𝑚) ar Knuta­Morisa­Prata algoritmu, kvantiski ̃ √𝑛 + √𝑚) = 𝑂( ̃ √𝑛) laika algoritms. Kaut gan zināms, ka vispārīgajā gadījumā ne­ eksistē 𝑂( √ pieciešami Ω( 𝑛) vaicājumi virknes simboliem, nav skaidrs, vai šī apakšējā robeža izpildās pie √ jebkuras m vērtības. Šajā darbā mēs pierādām, ka arī tad nepieciešami Ω( 𝑛) vaicājumi. Otrais uzdevums ir nosaukts ”visbiežāk sastopamas virknes meklēšana”: dotiem 𝑛 virknēm garumā 𝑘 √ ̃ pateikt, kāda virknē sastop…